註：本文同步刊載在Medium，若習慣Medium的話亦可去那邊看呦！

先來解答昨天的問題吧！

1. 假定有一個樓梯，你從第0階要爬到第n階，
   每次你只能選擇爬1階或者爬2階，這樣稱做一步。
   請寫出一個函式名為cs，給定n的値以後(n > 0)，
   計算出從第0階爬到第n階的方法共有幾種不同的變化？

上一篇提到了遞迴的關鍵點，首要在於將目標不斷簡化，
那麼我們該怎麼思考這題的簡化呢？
想想看，爬到第n階之前，應該要先爬到哪一階呢？
應該是n-1或n-2階吧？因為一次只能走一步和走兩步。
也就是說，假設我們知道cs(n-1)跟cs(n-2)，
我們就能知道cs(n)，因為它們兩個狀況只要分別走1步或2步就可以到達第n階，
而且cs(n-1)跟cs(n-2)彼此之間並沒有重複的走法。
所以cs(n) = cs(n-1) + cs(n-2)，
接下來的問題是，在什麼狀況下該停下來？
顯然，在n = 1及n = 2時，
cs(1)和cs(2)的值已經確定是1跟2了，
所以我們每次在遞迴時，只要碰到n=1或n=2時，就應該回傳n的值即可。

def cs(n):
    if n == 1 or n == 2:
        return n # 請留意一件事情，函式在使用return回傳以後，不論它當下是否處在迴圏或者是否往下還有東西未完成，都會直接離開函式並回傳值歐！
    return cs(n-1) + cs(n-2)

# 測試計算從cs(1)到cs(100)
for i in range(1, 101):
	print(cs(i))

這麼做其實有一個缺點：
比方說我們算cs(10)的時候，會拆分成cs(9)跟cs(8)，
而接下來會是：
cs(9) -> cs(8) + cs(7) -> cs(7) + cs(6) + cs(6) + cs(5) -> ...
cs(8) -> cs(7) + cs(6) -> cs(6) + cs(5) + cs(5) + cs(4) -> ...
在化簡的過程中，因為Python並不知道我們有重複的東西，
所以它並不會主動去幫我們把相同的cs(x)給結合在一起，
所以最終就會相當耗時。
(讀者可以執行)

那該怎麼改善呢？
這裡提供兩個方法。
方法一：將用過的答案先記下來(可以使用list或dict)

def cs(n, dic):
    # n在裡面就直接回傳(因為已經算過了!)
    if n in dic:
        return dic[n]
    # 先將n的結果算完再回傳，別忘了放到字典裡！
    dic[n] = cs(n-1, dic) + cs(n-2, dic)
    return dic[n]

dic = {1 : 1, 2 : 2} # 預設cs(1), cs(2)的結果
for i in range(1, 101):
	print(cs(i, dic))

方法二：lru_cache
lru_cahce是一個工具，
它可以記住函式已經計算過的內容，並存放起來。
在maxsize=None的時候，我們就不會限制它最多可以記幾個，
因此利用這個性質，它會幫我們自主處理重複計算的部分。

import functools
@functools.lru_cache(maxsize=None) # 用@開頭的稱為裝飾器，有興趣的讀者可再深入了解。
def cs(n):
    if n == 1 or n == 2:
        return n
    return cs(n-1) + cs(n-2)

for i in range(1, 101):
	print(cs(i))

那麼該如何做出迭代解呢？
由於cs(n)只跟cs(n-1)和cs(n-2)有關，
我們完全可以從cs(3)開始，一路往上加到結束。
1+2=3, 2+3=5, 3+5=8, ...以此類推。
當我們要算cs(n)時，表示我們需要經過n-2次的計算，
因此，我們只要利用兩個變數反覆交替並取代，
最終即可得到答案。

def cs(n):
    if n == 1 or n == 2: return n
    s1, s2 = 1, 2
    for i in range(n - 2):
        # Python的賦值是會一起看開始前的值來計算
        # 所以不會因為s1的值變s2了, s2新的值就變成s2+s2
        s1, s2 = s2, s1 + s2
    return s2

for i in range(1, 101):
    print(cs(i))

註：請留意當我們在使用字典或list時，其做為參數時是整包一起給，
但當傳一般的int時，傳入的值則當成另一個本地端的變數看待。

r = 33
def t1(r):
	print(r)
	r = 2
	print(r) # 改完變2

def t2(lt):
	print(lt)
	lt[0] = 100
	print(lt)

print('t1')
t1(r)
print(r) # 改完以後外面r的值還是33

print('\nt2')
lt = [555]
t2(lt)
print(lt) # 改完後lt內的值已經成為100了!

t1
33
2
33

t2
[555]
[100]
[100]

今天我們講點比較輕鬆的東西：模組和套件
如同前面我們所提過的，因為重複做相同的事情太麻煩了，
所以使用函式來將要重複做的事情寫在一起，可以反復呼叫。
那麼，如果你知道有些你需要做的事情，
已經有別人寫過了，用現成的當然會比自己寫還要快很多囉！

我們前面已經用過幾次import(匯入)了，
它的根本其實就是從你自己寫的程式，或者別人寫的程式(或函式庫)，
把前人的智慧來個拾人牙慧一下XD!
import的寫法大體有如下的變化：

import module # 直接將整個檔案納入(不用加.py)
from module import function # 只匯入function的部分
import module as xx # xx是自己選的名字，用來在這個程式中全程替代原先的module名
from module import function as oo # 這時候用oo就相當於跟function一樣

舉例來說，在Python中有一個內建模組叫random，random中的random()，
可以隨機生成一個0~1之間的小數亂數(包含0但不包含1)，
我們可以先import random，再呼叫random的random()函式來得到亂數；
或者，我們可以從random中取得random()函式，同時將其取一個別名。
(要為模組取別名也行，取別名的好處是可以比較簡短，且可以避免碰到名稱衝突的問題)

>>> import random
>>> random.random()
0.8076966930768202
>>> from random import random as rd
>>> rd()
0.23723453093568025

如果是Python內建的模組，那麼不論你的主要的程式.py檔放在哪都沒問題；
但如果你想要匯入的是別的檔案，那麼要將這些檔案放在同一個目錄下，
才能夠正常匯入。

如果我們要更嚴謹一點的話，就要使用套件的形式。
假設我們有一批寫好的檔案，他們都是這個主程式可能會用到的工具，
我們可能會開一個名為utils(工具箱)的資料夾，
裝入所有的檔案，比方說假設有check.py, schedule.py這兩個檔案。
除此以外，還要裝入一個至少是空白的檔案，必須取名為__init__.py。
(前後都有兩個底線)

所以我們的資料夾結構會變成這樣：
|--fromzero.py
|--utils
　　|--__init__.py
　　|--check.py
　　|--schedule.py

那我們來示範一下運作的模式：

# fromzero.py
from utils import check, schedule # 透過套件的模式來匯入
print("Check a lucky number: ", check.getLucky())
print("Check daily routine: ", schedule.get())

# utils/check.py
def getLucky():
    from random import random
    return int(random() * 7 + 1) # 取1~7之間的亂數

# utils/schedule.py
def get():
    return "You have a meeting today!" # 就只是回傳一段str而已

那我們一樣來練習題目吧！

1. 上次我們的猜數字遊戲本來是固定的數字，
   已知現在可以使用從random模組中的函式取得亂數法，
   (詳見Python Document https://docs.python.org/3/library/random.html)
   請利用random.randint(a,b)或random.random()，
   將前面的題目中要猜的數字改成隨機的1~100(含)之間的整數。

2. 承上題，1~100當中有一些數假設有我們想避開，不想被成為要猜的數字的話，
   若給定該串列avoid_lt = [4, 14, 44, 94]，
   請參照上面的說明，使用random.choice(seq)來處理。
   (random.choice()方法可以從一個序列型態的東西seq中隨機取出一個值)
   (序列是有順序的元素的集合統稱，比如list, tuple, range)
   提示：可以先新增一個數列並去處掉不要的元素再做random.choice()

辛苦啦！我們明天見！